package com.camus.verify.algorithm.impl;

import java.math.BigDecimal;
import java.util.concurrent.atomic.AtomicLong;

import com.camus.utils.BigDecimalUtils;
import com.camus.verify.algorithm.MatchTarget;
import com.camus.verify.algorithm.SubsetAlgorithm4BigDecimal;

public class SubsetAlgorithmOfSlideWindow4BigDecimal implements SubsetAlgorithm4BigDecimal {

	@Override
	public MatchTarget[] findSubsetWithinRange(MatchTarget[] candidateArr, BigDecimal lower, BigDecimal upper) {
		AtomicLong atomicLong = SubsetAlgorithm4BigDecimal.counter.get();
		// 算法复杂度为O(n*n)，可能找不到结果
		MatchTarget[] subsetArr = null;
		int len = candidateArr.length;

		// 前缀和
		BigDecimal[] prefixSumArr = new BigDecimal[len];
		prefixSumArr[0] = candidateArr[0].getTarget();
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1].add(candidateArr[i].getTarget());
		}

		// 滑动窗口大小为1...len
		loop: for (int winSize = 1; winSize <= len; winSize++) {
			// 滑动窗口大小为1
			if (winSize == 1) {
				for (int i = 0; i < len; i++) {
					atomicLong.getAndIncrement();
					if (BigDecimalUtils.isWithinRange(candidateArr[i].getTarget(), upper, lower) == 0) {
						subsetArr = new MatchTarget[] { candidateArr[i] };
						break loop;
					}
				}
				continue;
			}
			// 滑动窗口大小为2...len
			// 区间和[i,j] = prefixSum[j] - prefixSum[i-1]
			for (int startIdx = 0, endIdx = startIdx + winSize - 1; endIdx < len; startIdx++, endIdx++) {
				atomicLong.getAndIncrement();
				// 求区间和[startIdx,endIdx]
				BigDecimal sum = prefixSumArr[endIdx];
				if (startIdx > 0) {
					sum = sum.subtract(prefixSumArr[startIdx - 1]);
				}
				if (BigDecimalUtils.isWithinRange(sum, upper, lower) == 0) {
					subsetArr = new MatchTarget[winSize];
					for (int i = 0; i < winSize; i++) {
						subsetArr[i] = candidateArr[i + startIdx];
					}
					break loop;
				}
			}
		}
		return subsetArr;
	}

}
